1. Field of the Invention
The present invention relates to data processing, and in particular relates to methods and devices for image compression.
2. Description of the Related Art
The rapid growth of digital imaging applications, including desktop publishing, multimedia, teleconferencing, and high-definition television (HDTV) has increased the need for efficient and standardized image compression techniques. Without image compression, the transmission of images would require an unacceptable bandwidth in many applications. As a result, methods of compressing images have been the subject of numerous research publications. Image compression schemes convert an image consisting of a two-dimensional array of pixels into a sequence of bits which are to be transmitted over a communication link. Each pixel represents the intensity of the image at a particular location therein. The transmission link may be an ordinary telephone line.
Consider an image comprising a gray-scale representation of a photograph at a resolution of 1000.times.1000 lines. Each pixel typically consists of 8 bits which are used to encode 256 possible intensity levels at the corresponding point on the photograph. Hence, without compression, transmission of the photograph requires that 8 million bits be sent over the communication link. A typical telephone line is capable of transmitting about 9600 bits per second; hence the picture transmission would require more than 10 minutes. Transmission times of this magnitude are unacceptable.
As a result, image compression systems are needed to reduce the transmission time. It will also be apparent to those skilled in the art that image compression systems may also be advantageously employed in image storage systems to reduce the amount of memory needed to store one or more images.
The compression of an image typically requires two steps. In the first step, the image is transformed to a new representation in which the correlation between adjacent pixels is reduced. This transformation is usually completely reversible, that is, no information is lost at this stage. The number of bits of data needed to represent the transformed image is at least as large as that needed to represent the original image. The purpose of this transformation is to provide an image representation which is more ideally suited to known compression methods.
In the second step, referred to as quantization, each pixel in the transformed image is replaced by a value which is represented in fewer bits, on average, than the original pixel value. In general, the original gray scale is replaced by a new scale which has coarser steps and hence can be represented in fewer bits. The new gray scale typically has levels in which the different steps are of different sizes. The new gray scale is calculated from the statistical distribution of the pixel values in the transformed image.
The discrete cosine transform (DCT) is known as a basic technique among the transformations. For analysis of two-dimensional (2D) signals such as images, we need a 2D version of the DCT. Rather than taking the transformation of the images as a whole, the DCT is applied separately to 8×8 of 16×16 blocks of the image. However, due to the restriction of this size, it needs many line buffers for hardware implementation to reference the pixel value of 8 rows or 16 rows of the image at the same time. For example, the transformation of an 8×8 block needs 7 line buffers to temporarily store the pixel values of the other 7 rows of the image. Because of the line buffer requirement, the implementation cost of DCT-based image compression is difficult to decrease.